package com.zhugang.week05;

import java.util.HashSet;
import java.util.Set;

/**
 * @program algorithms
 * @description: intersectionNode
 * @author: chanzhugang
 * @create: 2022/07/08 12:18
 */
public class IntersectionNode2 {

    /**
     * 160 相交链表
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode intersectionNode(ListNode headA, ListNode headB) {
        // 哈希表缓存其中一个链表，遍历另一个链表看是否在缓存里
        Set<ListNode> set = new HashSet<>();
        ListNode p = headA;
        while (p != null) {
            set.add(p);
            p = p.next;
        }

        p = headB;
        while (p != null) {
            if (set.contains(p)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}